package com.xsherl.leetcode.solution;

import cn.hutool.core.lang.Assert;
import com.xsherl.leetcode.utils.ArrayUtils;
import com.xsherl.leetcode.utils.PrintUtils;

import java.util.ArrayList;
import java.util.List;

public class NQueens2 {

    /**
     * 回溯
     * 每行依次遍历列，判断皇后是否在有效位置
     * 优化方案：使用chars来存储皇后的位置
     */
    public int totalNQueens(int n) {
        char[][] chars = new char[n][n];
        boolean[] validIndexes = new boolean[n];
        for (int i = 0; i < n; ++i){
            validIndexes[i] = true;
        }
        return totalNQueens(0, n, chars, validIndexes);
    }

    public int totalNQueens(int index, int size, char[][] chars, boolean[] validIndexes) {
        if (index >= size) {
            return 1;
        }
        for (int i = 0; i < size; ++i) {
            chars[index][i] = '.';
        }
        int count = 0;
        for (int i = 0; i < size; ++i) {
            if (validIndexes[i] && isValid(chars, index, i)) {
                chars[index][i] = 'Q';
                validIndexes[i] = false;
                count += totalNQueens(index + 1, size, chars, validIndexes);
                chars[index][i] = '.';
                validIndexes[i] = true;
            }
        }
        return count;
    }

    public boolean isValid(char[][] chars, int i, int j) {
        int size = chars.length;
        for (int x = 0; x < size; ++x) {
            if (chars[x][j] == 'Q') {
                return false;
            }
        }
        for (int y = 0; y < size; ++y) {
            if (chars[i][y] == 'Q') {
                return false;
            }
        }
        int x = i;
        int y = j;
        while (x >= 0 && y >= 0) {
            if (chars[x--][y--] == 'Q') {
                return false;
            }
        }
        x = i;
        y = j;
        while (x >= 0 && y < size) {
            if (chars[x--][y++] == 'Q') {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int n = 4;
        int t = new NQueens2().totalNQueens(n);
        System.out.println(t);
    }

}
